Semi-supervised learning seeks to learn a machine learning model when only a small amount of the available data is labeled. The most wides pread approach uses a graph prior, which encourages similar instances to have si milar predictions. This has been very successful with models ranging from kernel mac hines to neural networks, but has remained inapplicable to decision trees, for which the optimization problem is much harder. W e solve this based on a reformulatio n of the problem which requires iteratively solving two simpler problems: a supervised tree learning problem, which can be solved by the Tree Alternating Opti mization algorithm; and a label smoothing problem, which can be solved through a s parse linear system. The algorithm is scalable and highly effective even wit h very few labeled instances, and makes it possible to learn accurate, interpr etable models based on decision trees in such situations.